/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._08_05;

/**
 *
 * 递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
 *
 * 示例1:
 *
 *  输入：A = 1, B = 10
 *  输出：10
 * 示例2:
 *
 *  输入：A = 3, B = 4
 *  输出：12
 * 提示:
 *
 * 保证乘法范围不会溢出
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._08_05
 * @ClassName: Multiply
 * @Author: linyaonan
 * @Date: 2020/3/27 14:58
 */
public class Multiply {

    public long multiply(int A, int B) {
        if (A == 1) {
            return B;
        }
        if (B == 1) {
            return A;
        }
        // 判断A与B那个一较少，作为循环数值，另一个作为基准
        int aCount = Integer.bitCount(A);
        int bCount = Integer.bitCount(B);
        int cycle;
        int base;
        if (aCount < bCount) {
            cycle = A;
            base = B;
        } else {
            cycle = B;
            base = A;
        }

        // 二进制数值
        String sC = Integer.toBinaryString(cycle);
        int indexCount = 0;
        long allCount = 0;
        char[] chars = sC.toCharArray();
        for (int i = chars.length - 1; i >= 0; i--) {
            char c = chars[i];
            if (c == '1') {
                allCount += base << indexCount;
            }
            indexCount++;
        }
        return allCount;
    }

}
